package com.algorithm.排序.基于比较的排序;

import com.algorithm.排序.Sort;

import java.util.ArrayList;
import java.util.List;

public class 希尔排序<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        //步长序列 {8,4,2,1}
        List<Integer> stepSequence = shellStepSequence();
        for (Integer step : stepSequence) {
            sort(step);
        }
    }

    /**
     * 分成step进行排序
     * @param step:步长
     */
    private void sort(int step){
        //col:第几列，column的简称
        for (int col = 0; col < step; col++) {//对第col列进行排序
            //假设元素在第 col 列、第 row 行，步长（总列数）是 step
            //那么这个元素在数组中的索引是 col + row * step
            //col，col+step，col+2*step，col+3*step
            for (int begin = col + step; begin < array.length; begin += step) {
                int  cur = begin;
                //从下标为一的地方开始比较，下标为0的元素像第一张扑克牌一样已经在手上了
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /**
     * 生成步长序列，使用希尔本人给出的生成步长序列的算法
     * 希尔本人给出的步长序列是 n/2^𝑘，比如 n 为16时，步长序列是{1, 2, 4, 8}
     */
    private List<Integer> shellStepSequence(){
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;

        while ((step >>= 1) > 0){
            stepSequence.add(step);
        }

        return stepSequence;
    }
}
